using System;
using System.Collections.Generic;
using System.Linq;

namespace LeetCode {
    public class Rectangle {
        public int MaximalRectangle (char[][] matrix) {
            if ((null == matrix) || (0 == matrix.Length)) {
                return 0;
            }
            int m = matrix.Length;
            int n = matrix[0].Length;
            int[, ] dp = new int[m, n];
            int maxS = 0;
            for (int i = 0; i < m; i++) {
                for (int j = n - 1; j >= 0; j--) {
                    if ((n - 1) == j) {
                        dp[i, j] = 0 == (matrix[i][j] - '0') ? 0 : 1;
                    } else {
                        dp[i, j] = 0 == (matrix[i][j] - '0') ? 0 : (1 + dp[i, j + 1]);
                    }
                }
            }
            for (int j = 0; j < n; j++) {
                Stack<int> stack = new Stack<int> ();
                for (int i = 0; i < m; i++) {
                    if (stack.Count == 0 || dp[i, j] >= dp[stack.Peek (), j]) {
                        stack.Push (i);
                        continue;
                    }
                    while (stack.Count != 0 && dp[i, j] < dp[stack.Peek (), j]) {
                        int idx = stack.Pop ();
                        if (stack.Count == 0) {
                            maxS = Math.Max (maxS, i * dp[idx, j]);
                        } else {
                            maxS = Math.Max (maxS, (i - stack.Peek () - 1) * dp[idx, j]);
                        }
                    }
                    stack.Push (i);
                }
                while (stack.Count != 0) {
                    int idx = stack.Pop ();
                    if (stack.Count == 0) {
                        maxS = Math.Max (maxS, m * dp[idx, j]);
                    } else {
                        maxS = Math.Max (maxS, (m - stack.Peek () - 1) * dp[idx, j]);
                    }
                }
            }
            return maxS;
        }
        public int MaximalRectangle1 (char[][] matrix) {
            if ((matrix.Length == 0) || (matrix[0].Length == 0)) {
                return 0;
            }
            int m = matrix.Length;
            int n = matrix[0].Length;
            int[] left = new int[n];
            int[] right = new int[n];
            int[] height = new int[n];
            int res = 0;
            right = Enumerable.Repeat (n, n).ToArray ();
            for (int i = 0; i < m; i++) {
                int cur_left = 0, cur_right = n;
                for (int j = 0; j < n; j++) {
                    height[j] = matrix[i][j] == '1' ? height[j] + 1 : 0;
                    left[j] = matrix[i][j] == '1' ? Math.Max (left[j], cur_left) : 0;
                    cur_left = matrix[i][j] == '1' ? cur_left : j + 1;
                }
                for (int j = n - 1; j >= 0; j--) {
                    right[j] = matrix[i][j] == '1' ? Math.Min (right[j], cur_right) : n;
                    cur_right = matrix[i][j] == '1' ? cur_right : j;
                }
                for (int j = 0; j < n; j++) {
                    res = Math.Max (res, (right[j] - left[j]) * height[j]);
                }
            }
            return res;
        }
        public int maximalRectangle (char[][] matrix) {
            if (matrix == null || matrix.Length == 0 || matrix[0] == null) {
                return 0;
            }
            int m = matrix.Length, n = matrix[0].Length;
            int[] l = new int[n];
            int[] r = new int[n];
            int[] h = new int[n];
            int result = 0;
            for (int i = 0; i < n; i++) {
                l[i] = 0;
                r[i] = n;
                h[i] = 0;
            }
            for (int i = 0; i < m; i++) {
                int cur_left = 0, cur_right = n;
                for (int j = 0; j < n; j++) {
                    if (matrix[i][j] == '1') {
                        h[j] += 1;
                    } else {
                        h[j] = 0;
                    }
                }
                for (int j = 0; j < n; j++) {
                    if (matrix[i][j] == '1') {
                        l[j] = Math.Max (l[j], cur_left);
                    } else {
                        l[j] = 0;
                        cur_left = j + 1;
                    }
                }
                for (int j = n - 1; j >= 0; j--) {
                    if (matrix[i][j] == '1') {
                        r[j] = Math.Min (r[j], cur_right);
                    } else {
                        r[j] = n;
                        cur_right = j;
                    }
                }
                for (int j = 0; j < n; j++) {
                    result = Math.Max (result, (r[j] - l[j]) * h[j]);
                }
            }
            return result;
        }
    }
}